# 36/100 二叉树-二叉树的中序遍历
# leetcode第94题: https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/26
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorderTraversal_rec(root: Optional[TreeNode]) -> list[int]:
    res = []

    def inorder_travel(r: Optional[TreeNode]):
        """递归函数"""
        if r:
            if r.left:
                inorder_travel(r.left)
            res.append(r.val)
            if r.right:
                inorder_travel(r.right)

    inorder_travel(root)
    return res


def inorderTraversal_stack(root: Optional[TreeNode]) -> list[int]:
    """除了递归以外还可以使用栈来代替递归"""
    res = []
    stack = []
    while stack or root:
        while root:  # 添加每个节点的左节点直到到叶节点
            stack.append(root)
            root = root.left
        root = stack.pop()  # 弹出
        if root:
            res.append(root.val)  # 读取
            root = root.right  # 遍历右节点
    return res


if __name__ == '__main__':
    t1 = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
    t2 = None
    t3 = TreeNode(1)
    t4 = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    print(inorderTraversal_rec(t1))
    print(inorderTraversal_rec(t2))
    print(inorderTraversal_rec(t3))
    print(inorderTraversal_rec(t4))
    print("=====" * 15)
    print(inorderTraversal_stack(t1))
    print(inorderTraversal_stack(t2))
    print(inorderTraversal_stack(t3))
    print(inorderTraversal_stack(t4))
